public class Solution2472 {
    public int maxPalindromes(String s, int k) {
        boolean[][] f=new boolean[s.length()][s.length()];
        for (int i=s.length()-1;i>=0;i--){
            f[i][i]=true;
            if (i+1<s.length() && s.charAt(i)==s.charAt(i+1)){
                f[i][i+1]=true;
            }
            for (int j=i+2;j<s.length();j++){
                if (s.charAt(i)==s.charAt(j)){
                    f[i][j]=f[i+1][j-1];
                }
            }
        }
        int[] g=new int[s.length()+1];
        for (int i=k-1;i<s.length();i++){
            g[i+1]=g[i];
            for (int j=i-k+1;j>=0;j--){
                if (f[j][i]){
                    g[i+1]=Math.max(g[i+1],g[j]+1);
                    break;
                }
            }
        }
        return g[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution2472().maxPalindromes("abaccdbbd",3));
    }
}
